package leetcode.to1000;

import org.junit.Test;

import java.util.*;

public class T0332 {
    //使用DFS正向的实现不正确
    int num;
    boolean flag=false;
    Map<String, PriorityQueue<String>> map = new HashMap<>();
    List<String> res=new LinkedList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        num = tickets.size();

        for (List<String> ticket : tickets) {
            if (map.containsKey(ticket.get(0))) {
                map.get(ticket.get(0)).add(ticket.get(1));
            } else {
                PriorityQueue<String> list = new PriorityQueue<>();
                list.add(ticket.get(1));
                map.put(ticket.get(0), list);
            }
        }
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("JFK");
        dfs("JFK", 0, linkedList);
        return res;
    }

    private void dfs(String s, int n, LinkedList<String> list) {
        if (n == num&&!flag) {
            flag=true;
            res=new LinkedList<>(list);
            return ;
        }
        while (!flag&&map.containsKey(s) && map.get(s).size() > 0) {
            String s1 = map.get(s).poll();
            list.add(s1);
            dfs(s1, n + 1, list);
            list.removeLast();
        }
    }

    @Test
    public void test() {
        List<List<String>> tickets = new ArrayList<>();
        List<String> list1 = new ArrayList<>();
        List<String> list2 = new ArrayList<>();
        List<String> list3 = new ArrayList<>();
        list1.add("JFK");
        list1.add("KUL");
        list2.add("JFK");
        list2.add("NRT");
        list3.add("NRT");
        list3.add("JFK");
        tickets.add(list1);
        tickets.add(list2);
        tickets.add(list3);
        //[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
        findItinerary(tickets);
    }
    class Solution2 {
        //使用优先队列，可以在DFS的时候直接找到最有的解
        Map<String, PriorityQueue<String>> map = new HashMap<>();
        List<String> itinerary = new LinkedList<>();

        public List<String> findItinerary(List<List<String>> tickets) {
            for (List<String> ticket : tickets) {
                String src = ticket.get(0), dst = ticket.get(1);
                if (!map.containsKey(src)) {
                    map.put(src, new PriorityQueue<>());
                }
                map.get(src).offer(dst);
            }
            dfs("JFK");
            Collections.reverse(itinerary);
            return itinerary;
        }

        public void dfs(String curr) {

            while (map.containsKey(curr) && map.get(curr).size() > 0) {
                //把邻居取出，进行dfs
                String tmp = map.get(curr).poll();
                dfs(tmp);
            }
            //当不符合条件，那么加入list
            //那么这个条件是什么呢？
            //无邻居，即叶结点
            itinerary.add(curr);
        }
    }
}
